/*
堆排序（Heap Sort）是一种不稳定排序算法，它的平均时间复杂度为 $O(n\log n)$，它的基本思想是将待排序的数组看成一棵完全二叉树，并将其构建成一个堆（Heap）这是第一步，
然后依次取出堆顶元素，将其与堆底元素交换，然后重新调整堆，直到堆中仅剩一个元素为止 这是第二步。堆排序需要额外的空间存储堆，因此空间复杂度为 $O(1)$。
 */

//nums为要排序的数组
const nums = [4,6,2,3,10,1]
function heapify(heap, i, len) {
    let max = i
    let left = 2 * i + 1
    let right = 2 * i + 2
    // 左孩子存在且比根大
    if (left < len && heap[left] > heap[max]) {
        max = left
    }
    // 右孩子存在且比根大
    if (right < len && heap[right] > heap[max]) {
        max = right
    }
    // 即需要更换
    if (max !== i) {
        [heap[i], heap[max]] = [heap[max], heap[i]]
        // 递归处理 (如根节点需要调整则必须比较整个下面的树进行调整，所以此处的递归是必须的)
        heapify(heap, max, len)
    }
}
//第一步 建立最大堆（升序）从最后一个非叶子节点开始
for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) {
    heapify(nums, i, nums.length)
}
console.log(nums)
//第二步 排序
for (let i = nums.length - 1; i >= 0; i--) {
    // 将尾叶子与根交换
    [nums[0], nums[i]] = [nums[i], nums[0]]
    // 然后开始排序
    heapify(nums, 0, i)
}
console.log(nums)
